#include <bits/stdc++.h>

using namespace std;

// 最小覆盖子串
// 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串
// 如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
// 测试链接 : https://leetcode.cn/problems/minimum-window-substring/


class Solution 
{
public:
    string minWindow(string s, string t) 
    {
        int m = s.size(), n = t.size();
        if(m < n) return "";

        int cnts[128]{};
        for(char ch : t) --cnts[ch];
        // 最小覆盖子串的长度
        int len = INT_MAX;
        // 从哪个位置开头，发现的这个最小覆盖子串
        int start = 0;
        for(int l = 0, r = 0, debt = n; r < m; ++r)
        {
            // s[r] 当前字符 -> int
            // cnts[s[r]] : 当前字符欠债情况，负数就是欠债，正数就是多给的
            if(cnts[s[r]]++ < 0) --debt;
            if(debt == 0)
            {
                // r位置结尾，真的有覆盖子串！
				// 看看这个覆盖子串能不能尽量短
                while(cnts[s[l]] > 0)
                {
                    // l位置的字符能拿回
                    --cnts[s[l++]];
                }
                // 从while里面出来
				// l....r就是r位置结尾的最小覆盖子串
                if(r - l + 1 < len)
                {
                    len = r - l + 1;
                    start = l;
                }
            }
        }
        return len == INT_MAX ? "" : s.substr(start, len);
    }
};


class Solution 
{
public:
    string minWindow(string s, string t) 
    {
        int m = s.size(), n = t.size();
        if(m < n) return "";

        // 统计每个字母出现的次数以及字符种类
        int cnt1[128]{}, cnt2[128]{}, kind = 0;
        for(char ch : t)
        {
            if(cnt1[ch]++ == 0) ++kind;
        }
        // minLen : 最小覆盖子串的长度
        // begin : 从哪个位置开头，发现的这个最小覆盖子串
        int minLen = m + 1, begin = -1, left = 0, right = 0, count = 0;
        while(right < m)
        {
            // in : 进窗口的字符
            char in = s[right];
            // 窗口内 in 的出现子串和 t 中 in 的出现次数相等,则 ++count
            if(++cnt2[in] == cnt1[in]) ++count;
            // 字符的种类相等,则窗口左移,减小窗口大小
            while(count == kind)
            {
                // 记录最小覆盖子串的长度和开始位置
                if(right - left + 1 < minLen)
                {
                    begin = left;
                    minLen = right - left + 1;
                }
                // out ： 出窗口的子串
                char out = s[left++];
                // 窗口内 out 的出现子串和 t 中 out 的出现次数相等,则 --+count
                if(cnt2[out]-- == cnt1[out]) --count;
            }
            ++right;
        }
        // begin 等于 -1，则表明没有最小覆盖子串
        if(begin == -1) return "";
        return s.substr(begin, minLen);
    }
};